import gmpy2
import libnum

p = 112454994630978850005784651276022327545786198205744597431888680937657203192943
q = 111081771780978300442208201256251933100607227308819156491182881723714968913833
c = 7847140580627012782899798457736961376953768684667159008470556786390887805253326211691923724846808704462396746105331991924048819814322540306282164012066426
dp = 99016059099144522019375365089687785694029213535292918424815544402513220169503
dq = 79504900574184798493105575420403885224379864982754477219462523963780735261625


def decrypt(dp, dq, p, q, c):
    InvQ = gmpy2.invert(q, p)
    mp = pow(c, dp, p)
    mq = pow(c, dq, q)
    m = (((mp - mq) * InvQ) % p) * q + mq
    print(mp - mq)
    print(libnum.n2s(int(m)).decode())


decrypt(dp, dq, p, q, c)
#
# m=pow(c,dp,p)
# m=pow(c,dq,q)
# #前提就是 m<p,m<q
# print(libnum.n2s(m))
